from typing import List
from collections import Counter


class Solution:
    """
    方法： findSubstring

    逻辑: 使用滑动窗口技术遍历字符串s，统计每个单词的出现次数，并检查是否所有单词都在窗口内出现了指定次数。

    Args:
        s (str): 输入字符串。
        words (List[str]): 单词列表。

    Returns:
        List[int]: 包含所有由words组成的子串在s中的起始索引。

    Time: O(n * m), 其中n是字符串s的长度，m是单词列表words的长度。

    Space: O(m), 用于存储单词频率表和当前窗口的单词频率表。
    """
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:return []
        wordsize = len(words[0])
        wordnum = len(words)
        n = len(s)
        if n < wordsize: return []
        cnt_words = Counter(words)
        res = []
        for i in range(0, wordsize):
            left, right, wordcnt = i, i, 0
            #存储窗口中单词
            tmp_counter = Counter()
            while right + wordsize <= n:
                w = s[right: right + wordsize]
                right += wordsize
                if w not in cnt_words:
                    # 无匹配窗口向右滑动
                    left = right
                    wordcnt = 0
                    tmp_counter.clear()
                else:
                    tmp_counter[w] += 1
                    wordcnt += 1
                    while tmp_counter[w] > cnt_words[w]:
                        t_w = s[left:left+wordsize]
                        tmp_counter[t_w] -= 1
                        left += wordsize
                        wordcnt -= 1
                    if wordcnt == wordnum:
                        res.append(left)
        return res
